#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Solution
{
private:
    class MyQueue{
    public:
        void push(int value){
            while (!_que.empty() && value > _que.back()){
                _que.pop_back();
            }
            _que.push_back(value);
        }

        void pop(int value){
            if(!_que.empty() && value == _que.front()){
                _que.pop_front();
            }
        }

        int getMaxValue(){
            return _que.front();
        }

    private:
        deque<int> _que; 
    };
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> res;
        MyQueue que;
        for (int i=0; i<k; i++){
            que.push(nums[i]);
        }
        for(int i=0; i<nums.size() - k; i++){
            res.push_back(que.getMaxValue());
            que.pop(nums[i]);
            que.push(nums[i+k]);
        }
        res.push_back(que.getMaxValue());
        return res;
    }
};